#ifndef   _HEAD_H_   
#define   _HEAD_H_  

#define ifdebug 0

typedef enum VertexColor
{
	//Vertex_RED = -1,	
	Vertex_WHITE = 0,	// 未被搜索到
	Vertex_BLACK = 1,	// 子结点都被搜索完毕
	Vertex_GRAY = 2	// 子结点正在被搜索
} VertexColor;

//邻接表元素
typedef struct GNode
{
	int number;	// 顶点编号
	struct GNode *next;
} GNode;
 
//顶点
typedef struct Vertex
{
	int number;         //顶点编号
	int f;			//记录其被访问的次序
	VertexColor color;	// 搜索过程标记搜索状态
	struct Vertex *p;
} Vertex;
 
typedef struct Graph
{
	GNode *LinkTable;//邻接表
	Vertex *vertex;
	int VertexNum;
} Graph;

//copy指令
typedef struct Copy
{
	off_t fd;
	off_t ff;
    off_t t;
    off_t l;
}Copy;

//add指令
typedef struct Add
{
	off_t fe;
    off_t t;
    off_t l;
}Add;

typedef struct Cmd
{
	int type;//0 for add,1 for copy
	off_t f;
	off_t t;
	off_t l;
}Cmd;


//block
typedef struct Block
{
	int cmdCount;
	int maxCmdCount;
	off_t startPos;
	off_t endPos;
	Cmd *cmds;
}Block;

Block newBlock(int start,int end,int maxCmdCount);
Cmd newAdd(off_t t,off_t l);
Cmd newCopy(off_t f,off_t t,off_t l);
int addCmdToBlock(Block *block,Cmd cmd);

//栈
typedef struct Stack {
	int value;
	struct Stack *pre;
	struct Stack *preGray;
} Stack;



/**
*函数名 : reOrder
*函数功能描述 :对block进行重排序，得到更新时的block执行顺序。
*函数参数 : 
*函数返回值 : 
**/
int reOrder(Block *blocks,int blockCount,int *order);


/**
*函数名 : searchByDepthFirst
*函数功能描述 : 用dfs遍历有向图，如果遇到环就破环其中的某个依赖关系。按访问的顺序对block重排序。
*函数参数 : 
*函数返回值 : 
**/
int searchByDepthFirst(Graph *g,int *order,Block *blocks,int **cost);


/**
*函数名 : findMinNodeInCycle
*函数功能描述 : 寻找破环代价最小的节点
*函数参数 : 
*函数返回值 : 
**/
void findMinNodeInCycle(Stack *s,int **cost,Vertex *v,int vn,int *blockf,int *blockt);

/**
*函数名 : transform
*函数功能描述 : 如果存在copy指令需要从blockf块复制到blockt块中，则将该copy转化为add指令
*函数参数 :
*函数返回值 :
**/
int transform(Block *blocks,int blockf,int blockt);

/**
*函数名 : ifConflict
*函数功能描述 : 是否存在Copy 从fblock复制数据到tblock，如果存在这样的copy则认为fblock块和tblock块发生冲突
*函数参数 :	
*函数返回值 : 1：发生冲突 ，0：没有冲突
**/
int ifConflict(Block *blocks,int fblock,int tblock);

//实现了栈的相关功能
Stack* initStack(void);
void push(Stack **s, int value);
int pop(Stack **s);
int peek(Stack *s);
int isEmpty(Stack *s);
void destroyStack(Stack **s);
void printStack(Stack *s);
#endif